package ee.homework.third;

import java.util.ArrayList;
import java.util.Queue;
import java.util.Random;
import java.util.concurrent.LinkedBlockingQueue;

public class RadixSort {

	private Random random;

	public static void main(String[] args) {
		RadixSort radix = new RadixSort();
		radix.run();
	}

	public void run() {
		random = new Random();
		int k = 1000000;
		int[] radixList = new int[k];
		int tmp;
		int max = 0;
		for (int j = 0; j < k; j++) {
			tmp = random.nextInt(10);
			radixList[j] = tmp;
			if (max < tmp)
				max = tmp;
		}

		int length = String.valueOf(max).length();
		long time = System.currentTimeMillis();
		sort(radixList, length);
		System.out.println(System.currentTimeMillis() - time);
	}

	public void sort(int[] array, int d) {
		ArrayList<Queue<Integer>> buckets = new ArrayList<Queue<Integer>>(10);
		for (int i = 0; i < 10; i++) {
			buckets.add(new LinkedBlockingQueue<Integer>());
		}
		for (int i = 0; i < d; i++) {
			for (int j = 0; j < array.length; j++) {
				buckets.get(getDigit(array[j], i)).offer(array[j]);
			}
			int index = 0;
			for (Queue<Integer> queue : buckets) {
				while (!queue.isEmpty()) {
					array[index] = queue.poll();
					index++;
				}
			}
		}
	}

	public int getDigit(int value, int place) {
		int divider = (int) Math.pow(10, place);
		return value / divider % 10;
	}
}
